package someTestExcemple.huaweiOd.greedyMethod;

//华为OD机试 - 最长回文字符串 - 贪心算法（Java 2024 E卷 100分）
//https://blog.csdn.net/guorui_java/article/details/142664565

import java.util.*;
import java.util.stream.Stream;

public class TheLongestPalindromeStrin {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取输入字符串
        String input = scanner.nextLine();
        scanner.close();

        // 调用构造最长回文串的方法
        String palindrome = constructLongestPalindrome(input);
        // 输出结果
        System.out.println(palindrome);
    }

//    解题思路
//    统计字符频率：
//    遍历输入字符串，统计每个字符出现的次数。
//    由于字符串仅包含大小写字母，
//    可以使用一个固定大小的数组（如52个元素，分别对应’A’-‘Z’和’a’-‘z’）来高效地记录每个字符的出现次数。
//    构造回文串的左半部分：
//    遍历所有字符，按照字典序从小到大处理。
//    对于每个字符，取其出现次数的一半（即能组成的字符对数），并将这些字符按顺序添加到回文串的左半部分，
//    记得更新使用后的字符出现次数。
//    这样确保左半部分是字典序最小的，同时也保证了回文串的最大长度。
//    选择回文串的中间字符（如果有）：
//    在所有字符中，选择字典序最小且出现次数为奇数的字符，作为回文串的中间字符。
//    这一步是为了在无法完全对称的情况下，尽可能地增加回文串的长度，同时保持字典序最小。
//    构造回文串的右半部分：
//    将左半部分进行逆序，得到右半部分。
//    最终的回文串由左半部分、中间字符（如果有）和右半部分组成。
//    综合拼接：
//    拼接左半部分、中间字符和右半部分，得到最终的回文串。

    /**
     * 构造最长回文串
     *
     * @param s 输入字符串
     * @return 构造出的最长回文串
     */
    public static String constructLongestPalindrome(String s) {
        //A-Z=65-90 a-z 97-122
        // 创建一个大小为52的数组，分别对应'A'-'Z'和'a'-'z'
        //0-25存A-Z 26-51存a-z，值为出现的次数
        int[] count = new int[52];
        for (char c : s.toCharArray()) {
            if (c >= 'A' && c <= 'Z') {
                count[c - 'A']++;
            } else if (c >= 'a' && c <= 'z') {
                count[26 + c - 'a']++;
            }
        }

        StringBuilder left = new StringBuilder(); // 回文串的左半部分
        StringBuilder middle = new StringBuilder(); // 回文串的中间字符（如果有的话）

        // 遍历所有字符，按照字典序
        for (int i = 0; i < 52; i++) {
            // 计算当前字符可以使用的对数
            int pairs = count[i] / 2;
            //比如a出现3次，可以两边各放一个
            //如果是1就不能拼左右两边，只能尽量拼中间，超过1的奇数，左右两边都可以放一半
            if (pairs > 0) {
                // 获取字符
                char currentChar = indexToChar(i);
                // 将字符对添加到左半部分
                for (int j = 0; j < pairs; j++) {
                    left.append(currentChar);
                }
                // 更新剩余的字符数
                count[i] -= pairs * 2;
            }
        }
        // 查找可以作为中间字符的最小字符
        for (int i = 0; i < 52; i++) {
            if (count[i] > 0) {
                // 选择字典序最小的字符作为中间字符
                middle.append(indexToChar(i));
                break;
            }
        }

        // 构造完整的回文串
        StringBuilder right = new StringBuilder(left).reverse(); // 右半部分为左半部分的逆序
        left.append(middle).append(right); // 拼接左半部分、中间字符和右半部分

        return left.toString();
    }

    /**
     * 将索引转换为对应的字符
     *
     * @param index 字符索引（0-51）
     * @return 对应的字符
     */
    public static char indexToChar(int index) {
        if (index < 26) {
            return (char) ('A' + index);
        } else {
            return (char) ('a' + index - 26);
        }
    }
}
